package com.yamed.arithmetic;

import java.util.*;

/**
 *
 * 三个杯子 一个8L 一个5L 一个3L, 8L杯子满水，三个杯子没有刻度，最后倒出4L的水。
 *
 * @Author: wchen
 * @Description:
 * @Date: Created in 2019-08-30 09:01
 * Copyright 本内容仅限于杭州阿拉丁信息科技股份有限公司内部传阅，禁止外泄以及用于其他的商业目的
 */
public class CupAllocation {

    private final int MATCHER_RESULT = 4;
    private final int [] caps = {8, 5, 3};


    public static void main(String[] args) {
        CupAllocation cupAllocation = new CupAllocation();
        cupAllocation.allocation();
    }


    /**
     * 分配
     */
    public void allocation(){
        int [] cupWaters = {8, 0, 0};
        //构建父结点
        Element root = new Element();
        Element element = new Element(0, cupWaters, root);
        List<Element> elements = new ArrayList<>();
        elements.add(element);
        root.setChildrenList(elements);

        pourWater(root);
    }

    /**
     * 倒水
     * @param root
     */
    private void pourWater(Element root){
        List<int[]> matcherList = new ArrayList<>();
        matcherList.add(root.getValue());
        List<Element> childrenList = root.getChildrenList();
        while (!childrenList.isEmpty()){
            List<Element> newElements = new ArrayList<>();

            for (Element element : childrenList) {
                int[] ints = element.getValue();
                List<Element> allocationChildrenList = new ArrayList<>();
                List<Element> endElements = new ArrayList<>();
                for(int i=0; i<ints.length; i++){
                    List<int[]> allocationResult = allocationResult(i, ints, element);
                    //结果包装成element
                    for (int[] ints1 : allocationResult) {
                        Element ele = new Element(element.getLower() + 1, ints1, element);
                        if(!isEndElement(ele)){
                            allocationChildrenList.add(ele);
                        }else{
                            endElements.add(ele);
                        }
                    }
                }
                newElements.addAll(allocationChildrenList);
                if(!endElements.isEmpty()){
                    allocationChildrenList.addAll(endElements);
                }
                element.setChildrenList(allocationChildrenList);
            }
            childrenList = newElements;
        }

        System.out.println("*****************************************************************");
        root.printAllElement();

    }

    /**
     * 分配结果
     * @param currentIndex
     * @param cupWaters
     * @param element
     * @return
     */
    private List<int[]> allocationResult(int currentIndex, int [] cupWaters, Element element){
        int currentCapWater = cupWaters[currentIndex];
        List<int[]> currentResult = new ArrayList<>();
        for(int i=0; i<cupWaters.length; i++){
            //当前水杯，skip
            if(i == currentIndex){
                continue;
            }

            int optWater = cupWaters[i];
            //水杯已满，skip
            if(isFull(i, optWater)){
                continue;
            }

            //倒水
            int[] copyCupWaters = Arrays.copyOf(cupWaters, cupWaters.length);
            copyCupWaters = pourWater(currentIndex, i, copyCupWaters);

            //不存在之前的路径
            if(!element.contains(copyCupWaters)){
                currentResult.add(copyCupWaters);
            }
        }
        return currentResult;
    }


    /**
     * 水杯是否已满
     * @param currentIndex
     * @param currentCapWater
     * @return
     */
    private Boolean isFull(int currentIndex, int currentCapWater){
        int maxWater = caps[currentIndex];
        if(currentCapWater == maxWater){
            return Boolean.TRUE;
        }
        return false;
    }

    /**
     * 水杯是否为空
     * @param currentCapWater
     * @return
     */
    private Boolean isEmpty(int currentCapWater){
        return currentCapWater == 0;
    }

    /**
     * 倒水
     * @param oriCup
     * @param targetCup
     * @param cupWaters
     * @return
     */
    private int[] pourWater(int oriCup, int targetCup ,int [] cupWaters){
        int oriWater = cupWaters[oriCup];
        //目标水杯可操作的水量
        int targetWater = cupWaters[targetCup];
        int targetMaxWater = caps[targetCup];
        int residueWater = targetMaxWater - targetWater;

        if(oriWater >= residueWater){
            int newOriWater = oriWater - residueWater;
            int newTargetWater = targetMaxWater;
            cupWaters[oriCup] = newOriWater;
            cupWaters[targetCup] = newTargetWater;
        }else{
            int newOriWater = 0;
            int newTargetWater = targetWater + oriWater;
            cupWaters[oriCup] = newOriWater;
            cupWaters[targetCup] = newTargetWater;
        }
        return cupWaters;
    }

    /**
     * 是否已完成
     * @param element
     * @return
     */
    private Boolean isEndElement(Element element){
        int[] ints = element.getValue();
        for (int anInt : ints) {
            if(anInt == MATCHER_RESULT){
                return Boolean.TRUE;
            }
        }
        return Boolean.FALSE;
    }


    class Element {
        private int lower;
        private List<Element> childrenList;
        private Element parent;
        private int[] value;

        Element(){}

        Element(int lower, int[] value, Element parent){
            this.lower = lower;
            this.value = value;
            this.parent = parent;
        }

        /**
         * 判断是否否包含
         * @param value
         * @return
         */
        public Boolean contains(int[] value){
            Element parent = this;
            if(parent == null){
                return false;
            }

            while (parent != null){
                if(parent != null) {
                    int[] parentValue = parent.getValue();
                    if (compareValue(value, parentValue)) {
                        return Boolean.TRUE;
                    }
                }
                parent = parent.getParent();
            }
            return Boolean.FALSE;
        }

        /**
         * 值比较
         * @param value1
         * @param value2
         * @return
         */
        private Boolean compareValue(int[] value1, int[] value2){
            if(value1 == null || value2 == null){
                return Boolean.FALSE;
            }
            if(value1.length != value2.length){
                return Boolean.FALSE;
            }
            for(int i=0; i< value1.length; i ++){
                int v1 = value1[i];
                int v2 = value2[i];
                if(v1 != v2){
                    return Boolean.FALSE;
                }
            }
            return Boolean.TRUE;
        }

        /**
         * 打印所有路径
         */
        public void printAllElement(){
            List<Element> lastElements = getLastElement(this);

            for (Element lastElement : lastElements) {
                printElementRout(lastElement);
            }
        }

        /**
         * 结点的路径
         */
        public void printElementRout(Element element){
            StringBuilder builder = new StringBuilder(element.formatValue());
            Element parent = element.getParent();
            while (parent != null){
                builder.append(parent.formatValue());
                parent = parent.getParent();
            }
            System.out.println(builder.toString());
        }

        /**
         * 结点的路径
         */
        public void printElementRout(){
            StringBuilder builder = new StringBuilder(this.formatValue());
            Element parent = this.getParent();
            while (parent != null){
                builder.append(parent.formatValue());
                parent = parent.getParent();
            }
            System.out.println(builder.toString());
        }

        /**
         * 获取树的最后结点列表
         * @param element
         * @return
         */
        public List<Element> getLastElement(Element element){
            List<Element> lastElements = new ArrayList<>();
            if(element.hasNext()){

                List<Element> elements = element.getChildrenList();
                for (Element element1 : elements) {
                    List<Element> list = getLastElement(element1);
                    if(!list.isEmpty()){
                        lastElements.addAll(list);
                    }
                }
            }else{
                lastElements.add(element);
            }
            return lastElements;
        }

        public Boolean hasNext(){
            return this.childrenList != null;
        }

        public Boolean hasParent(){
            return this.parent != null;
        }

        public int getLower() {
            return lower;
        }

        public void setLower(int lower) {
            this.lower = lower;
        }

        public List<Element> getChildrenList() {
            return childrenList;
        }

        public void setChildrenList(List<Element> childrenList) {
            this.childrenList = childrenList;

        }

        public Element getParent() {
            return parent;
        }

        public void setParent(Element parent) {
            this.parent = parent;
        }

        public int[] getValue() {
            return value;
        }

        public void setValue(int[] value) {
            this.value = value;
        }

        public String formatValue(){
            StringBuilder sb = new StringBuilder("[");
            if(this.value != null) {
                for (int i : this.value) {
                    sb.append(i).append(" ");
                }
                sb.append("] <——");
                return sb.toString();
            }
            return "";
        }
    }


}
